package io.github.hadyang.leetcode.offer;

import java.util.ArrayList;
import org.junit.Test;

/** @author haoyang.shi */
public class FindNumbersWithSum {

  @Test
  public void test() {
    System.out.println(FindNumbersWithSum(new int[] {1, 2, 3, 4, 5, 7}, 5));
  }

  public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
    ArrayList<Integer> res = new ArrayList<>();

    if (array == null || array.length == 1) {
      return res;
    }

    int start = 0, end = array.length - 1;
    int minMulti = Integer.MAX_VALUE;
    int a = -1, b = -1;

    while (start < end) {
      int t = array[start] + array[end];
      if (t == sum) {
        int multi = array[start] * array[end];
        if (multi < minMulti) {
          a = array[start];
          b = array[end];
          minMulti = multi;
        }
        start++;
        end--;
      } else if (t > sum) end--;
      else start++;
    }

    if (a == -1 || b == -1) {
      return res;
    }

    res.add(a);
    res.add(b);

    return res;
  }
}
